A computer network typically comprises a plurality of interconnected nodes. A node may consist of any device, such as a host, endstation, server, etc., that transmits or receives data frames. A common type of network is a local area network ("LAN") which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol (LAN standard), such as Token Ring or Ethernet, that defines the functions performed by the data link and physical layers of a communications architecture (i.e., a protocol stack), such as the Transport Control Protocol/Internet Protocol (TCP/IP) Reference Model.
In a token ring network, each node or endstation is connected to a physical ring that carries data frames transmitted by the various stations in a single direction. Each station, moreover, acts like a repeater, transmitting all received data frames to the next station on the ring. The right to transmit data on the ring is controlled by a token, which continuously traverses the ring. A token that permits data transmission is referred to a free token. When a station receives the free token and has data to send, it changes the token's configuration to that of a busy token and attaches the busy token to the data frames being sent. As each data frame returns to the sending station, it is removed from the ring. Upon receipt of the last data frame, the sending station transmits a free token to the next station which may, in turn, transmit its own data frames. To simplify network maintenance and troubleshooting, each station is typically connected to the ring through a central concentrator.
Often, it is desirable to connect multiple token ring LANs together and thereby allow the endstations from one ring to exchange information with endstations on other rings. One or more intermediate devices are often used to interconnect multiple token ring LANs. For example, a bridge may be used to provide a "bridging" function between two or more token ring LANs. Alternatively, a switch may be utilized to provide a "switching" function for transferring information between a plurality of token ring LANs. Typically, the bridge or switch is a computer and includes a plurality of ports that couple the device to the token ring LANs.
Token Ring Routing Methods
There are basically two methods of routing frames across multiple interconnected token ring LANs. The first is referred to as source-route bridging (SRB). With source-route bridging, endstations are responsible for determining the route or path to be following through the network in order to reach a desired endstation. The endstations are also responsible for inserting this route information into a routing information field (RIF) of each source-route data frame being sent. The RIF is an ordered list of ring number/bridge number pairs through which the frame is to pass as it traverses the network. When such a frame is received by an SRB bridge, the contents of the RIF are examined to determine whether its entry port's ring number and its bridge number appear in the RIF field. If so, the SRB bridge forwards the frame to the destination port that is coupled to the ring number paired with its bridge number. However, if this ring number already appears in the RIF (e.g., it is paired with some other bridge number), then the frame is dropped since it presumably traversed that ring prior to reaching this SRB bridge. SRB bridges also drop any frames that do not contain an RIF.
In order to determine a path to a particular receiving station, a sending station transmits an explorer frame, such as an all routes explorer frame. SRB bridges receiving an explorer frame add routing information to the frame and forward it out all ports, other than the port on which it was received. The receiving station will thus receive multiple explorer frames, each carrying different routing information. The receiving station examines all of these explorer frames to identify the best (typically the shortest) path to the sending station. This path information is then returned to the sending station so that it may be used in any subsequent messages. With this routing scheme, SRB bridges need not maintain routing tables. All that is required is that each SRB bridge know its unique bridge identifier and the token ring numbers of each ring to which it is attached.
The other routing method is known as transparent routing. With transparent routing, a sending station does not know the path a frame should follow to reach other stations. Instead, the sending station inserts the receiving station's Media Access Control (MAC) address (known as the destination address) and its own MAC address (known as the source address) into each frame. A transparent bridge that receives the frame examines the destination address to identify the destination port onto which the frame should be forwarded. Transparent bridges typically learn which destination port to use for a given destination address by noting on which source port the latest message originating from that entity was received. This information is then stored by each bridge in a block of memory known as a filtering database. Thereafter, when a message is received on a source port, the bridge looks up the destination address in its filtering database and identifies the appropriate destination port for reaching the respective endstation. If no destination port is identified in the filtering database, the bridge floods the message out all ports, other than the source port.
The Institute of Electrical and Electronics Engineers (IEEE) has promulgated a standard, the 802. 1D standard, which governs the design and operation of bridges. This standard calls for bridges to have the capability to operate in either a source-route or a transparent mode, depending on the type of frame that it receives. That is, if the data frame includes an RIF, then the source-route transparent (SRT) bridge operates in a source-route mode with respect to this frame. If the frame does not include a RIF, the SRT bridge operates in a transparent mode by examining the destination MAC address of the frame and performing a look-up in its filtering database. Although this standard has been widely adopted, many token ring networks, especially those corresponding to the IBM Corporation token ring architecture, still utilize intermediate devices (referred to herein as legacy bridges or legacy devices) that operate only in the SRB mode.
Most computer networks also include redundant communications paths so that a failure of any given link does not isolate any portion of the network. The existence of redundant links, however, often results in the formation of circuitous paths or "loops" within the network which are highly undesirable because messages may traverse the loops indefinitely. The resulting traffic effectively overwhelms the network. For example, SRT bridges, as described above, replicate messages whose destination ports are not known or which contain broadcast or multicast destination addresses, resulting in a proliferation of data frames along any loops. Similar problems may occur with broadcast or multicast messages in networks operating in the SRB mode.
Spanning Tree Algorithm
To avoid the formation of loops, most intermediate devices execute a spanning tree algorithm, which allows them to calculate an active network topology that is loop-free (i.e., a tree) and yet connects every pair of LANs within the network (i.e., the tree is spanning). In general, by executing the spanning tree algorithm, bridges elect a single bridge to be the "root" bridge. Since each bridge has a unique numerical identifier (bridge ID), the root is typically the bridge with the lowest bridge ID. In addition, for each token ring coupled to more than one bridge, only one (the "designated bridge") is elected to forward frames to and from the respective ring toward the root bridge. The designated bridge is typically the one closest to the root. Each bridge also selects one port (the "root port") which gives the lowest cost path to the root. The root ports and designated bridge ports are selected for inclusion in the active topology and are placed in a forwarding state so that data frames may be forwarded to and from these ports and thus onto the corresponding paths or links of the network. Ports not included within the active topology are placed in a blocking state. When a port is in the blocking state, data frames will not be forwarded to or received from the port.
To obtain the information necessary to run the spanning tree algorithm, bridges exchange special messages called bridge protocol data unit (BPDU) frames. Each BPDU message has a plurality of fields, including a root identifier field (containing the identifier of the bridge assumed to be the root), a bridge identifier field (containing the identifier of the bridge sending the BPDU), a root path cost field (representing the cost to reach the assumed root from the port on which the BPDU is sent) and a port identifier field (containing the port number of the port on which the BPDU is sent). Upon receipt of a BPDU message, its contents are examined and compared with similar information (e.g., assumed root and lowest root path cost) stored by the receiving bridge. If the information from the received BPDU is "better" than the stored information, the bridge adopts the better information and uses it in the BPDUs that it sends (adding the cost associated with the receiving port to the root path cost) from its ports, other than the port on which the "better" information was received. Although BPDU messages are never forwarded by bridges, the identifier of the root is eventually propagated to and adopted by all bridges as described above, allowing them to select their root port and designated port(s).
In response to network topology changes (e.g., the addition or removal of intermediate devices or links), the active topology is recalculated. Ports that were in the blocking state may need to transition to the forwarding state and ports in the forwarding state may need to transition to the blocking state. Rather than transition directly from blocking to forwarding, the IEEE standard specifies that ports transition between two intermediate states (listening and learning). The IEEE standard also specifies that data messages are not to be forwarded while a port is in the listening or learning states.
Operation of the spanning tree algorithm is well-known to those skilled in the art and is set forth in the IEEE 802. 1D standard, which further provides that BPDUs are to be sent to a specific bridge multicast destination address. Bridges that comply with the 802.1D standard, moreover, are configured to recognize messages with this particular destination address as BPDU messages. Although many SRB bridges also implement a spanning tree protocol for detecting and blocking loops, as described above, they utilize a different bridge multicast destination address than that specified in the IEEE 802.1D standard. The destination address utilized by these SRB bridges typically corresponds to the address specified by the IBM Corporation for its token ring architecture. These IBM compliant BPDU messages also include a route designator in place of the port identifier field. Accordingly, difficulties have arisen when token ring networks having both SRT and SRB bridges are interconnected.
Dedicated Token Ring Bridges
To extend the capabilities of token ring bridges, the IEEE has promulgated the Dedicated Token Ring (DTR) bridge standard in Annex K to the IEEE 802.5 standard governing token ring LANs. The DTR standard establishes a hierarchical bridging arrangement and allows bridge ports to emulate concentrator ports, thereby eliminating the need to connect bridges to concentrators. Specifically, each bridge defines one or more Bridge Relay Functions (BRFs) and one or more Concentrator Relay Functions (CRFs) each of which performs a different bridging function. For example, each CRF interconnects a plurality of physical token ring segments into one logical token ring that has a single ring number. The CRF forwards data messages from one token ring segment to another. The BRF supports bridging between different CRFs. That is, rather than or in addition to forwarding a data message to another token ring segment, a first CRF may pass the message up to its associated BRF. The BRF, in turn, may forward the data message to a second CRF that is also coupled to the BRF. The second CRF may then forward the data message onto one of its token ring segments for receipt by a particular endstation. Thus, the BRF allows data messages to be transferred between different token ring numbers.
FIG. 1 is a highly schematic diagram of a conventional DTR compliant bridge 100. As shown, the DTR bridge 100 has multiple BRF entities 102-104 and multiple CRF entities 106-114. Each BRF 102-104, moreover, is associated with several CRFs 106-114 and each CRF includes a plurality of concentrator ports 116. For example, BRF 102 (also identified as BRF A) is associated with CRFs 106-108 (also identified as CRFs 1 and 2, respectively). Each CRF 106-114, moreover, is connected to multiple token ring segments 118 through its concentrator ports 116. Nonetheless, all of the token ring segments 118 connected to a single CRF (e.g., CRF 106) have a single token ring number (e.g., Token Ring 1). Each CRF 106-114 also has an internal port 120 for communicating with its associated BRF 102-104.
The DTR standard provides that each CRF is to participate in the spanning tree algorithm. That is, each concentrator port of a given CRF may transition between the blocking and forwarding states, depending on the information contained in BPDU messages received by the CRF. The format of these BPDU messages, moreover, corresponds to the IEEE 802.1D standard as described above. Nonetheless, the DTR standard is silent as to whether the BRFs should participate in the spanning tree algorithm and, if so, how that might be implemented, especially in view of the CRF's participation in the spanning tree algorithm. In addition, depending on the particular network configuration, loops may be present between various DTR bridges at the BRF level that are not blocked by execution of the spanning tree algorithm at the CRF level. Accordingly, a need has arisen for detecting and eliminating loops at both the CRF and BRF levels of a DTR bridge.
Additionally, particular token ring segments of a DTR bridge may be interconnected with other bridges that are not DTR compliant, including legacy SRB bridges. This may result in the occurrence of a loop passing through one of the CRFs of the DTR bridge. If the execution of the conventional spanning tree algorithm results in one of the CRF's concentrator ports being placed in the blocking state, connectivity may be lost between segments of the corresponding logical token ring. That is, with the concentrator port blocked, messages from one token ring segment must pass through the legacy SRB bridge to reach the next ring segment. SRB bridges, however, drop messages (including all routes explorer frames) when the RIF already includes the ring number paired with the identifier of the SRB bridge. This may cause a loss of connectivity between endstations associated with the same token ring number but residing on different token ring segments.